<head>
    <meta charset="UTF-8">
<title>算法提高 金明的预算方案</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div>【问题描述】</div>
<div>金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：&ldquo;你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行&rdquo;。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：</div>
<table width="200" border="1" cellpadding="1" cellspacing="1">
    <tbody>
        <tr>
            <td>主件</td>
            <td>附件</td>
        </tr>
        <tr>
            <td>电脑</td>
            <td>打印机，扫描仪</td>
        </tr>
        <tr>
            <td>书柜</td>
            <td>图书</td>
        </tr>
        <tr>
            <td>书桌</td>
            <td>台灯，文具</td>
        </tr>
        <tr>
            <td>工作椅</td>
            <td>无</td>
        </tr>
    </tbody>
</table>
<div>&nbsp;</div>
<div>如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。</div>
<div>设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j_1，j_2，&hellip;&hellip;，j_k，则所求的总和为：</div>
<div>v[j_1]*w[j_1]+v[j_2]*w[j_2]+ &hellip;+v[j_k]*w[j_k]。（其中*为乘号）</div>
<div>请你帮助金明设计一个满足要求的购物单。</div>
<div>【输入文件】</div>
<div>输入文件budget.in 的第1行，为两个正整数，用一个空格隔开：</div>
<div>N &nbsp;m</div>
<div>（其中N（&lt;32000）表示总钱数，m（&lt;60）为希望购买物品的个数。）</div>
<div>从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数</div>
<div>v &nbsp;p &nbsp;q</div>
<div>（其中v表示该物品的价格（v&lt;10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q&gt;0，表示该物品为附件，q是所属主件的编号）</div>
<div>【输出文件】</div>
<div>输出文件budget.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（&lt;200000）。</div>
<div>【输入样例】</div>
<div>1000 5</div>
<div>800 2 0</div>
<div>400 5 1</div>
<div>300 5 1</div>
<div>400 3 0</div>
<div>500 2 0</div>
<div>【输出样例】</div>
<div>2200</div>
<div>&nbsp;</div>
<p>&nbsp;</p>